package com.arron.algorithm.leetcodetop100.二分查找;

/**
 * @Classname GetNumberOfK
 * @Date 2020/9/13 15:42
 * @Created by 刘
 *
 * 题目：统计在一个升序的数组中，一个数的出现的次数
 *
 */
public class 统计数组中出现的次数 {

    public static void main(String[] args) {
        int[] a = {3,3,3,3,4,5};
        System.out.println(binarySearch(a, 3));
    }

    /**
     * 二分查找
     */
    public static int binarySearch(int[] arry,int k){

        int left = 0;
        int right = arry.length - 1;
        int mid;
        int num = 0;
        while (left<=right){
            mid = left + (right - left)/2;
            if (arry[mid] > k){
                right = mid -1;
            }
            if (arry[mid] < k){
                left = mid +1;
            }

            //找到目标值
            if (arry[mid] == k){
                int x= mid;
                //循环去找右边界，并统计数字出现的次数
                while (x<arry.length){
                    if (arry[x] !=k){
                        break;
                    }
                    x++;
                    num++;
                }
                x=mid;
                //循环去找到左边界，并统计出现的次数
                while (x>=0){
                    if (arry[x] !=k){
                        break;
                    }
                    x--;
                    num++;
                }
                return num-1;
            }
        }
        return 0;
    }

}
